第一章 数值分析与科学计算引论

1.2 数值计算的误差

• 误差来源与分类

  • 模型误差：数学模型与实际问题之间的误差.

  • 观测误差：物理量与观测值之间的误差.

  • 截断误差（方法误差）：近似解与精确解之间的误差.

  • 舍入误差：四舍五入、进制转换的误差.

• 约定

  • 准确值：$x$$x$.

  • 近似值：$x^{\ast }$$x^*$.

• 误差衡量

  • 有量纲

    • 绝对误差：$e^{\ast }=x^{\ast }-x$$e^* = x^* - x$.

    • 绝对误差限：${\epsilon }^{\ast }$$\ve^*$ 是 $e^{\ast }$$e^*$ 的上界.

  • 备注

    • 不等式简写：$x=x^{\ast }\pm {\epsilon }^{\ast }$$x = x^* \pm \ve^*$.

    • 一般写为：${\epsilon }^{\ast }=0.5\times {10}^{-n}$$\ve^* = 0.5 \cp 10^{-n}$.

  • 无量纲

    • 相对误差：$e_{\mathrm{r}}^{\ast }={\displaystyle \frac{e^{\ast }}{x}}$$e_\rm r^* = \dfrac{e^*}{x}$ 或 ${\displaystyle \frac{e^{\ast }}{x^{\ast }}}$$\dfrac{e^*}{x^*}$.

    • 相对误差限：${\epsilon }_{\mathrm{r}}^{\ast }={\displaystyle \frac{{\epsilon }^{\ast }}{\left|x^{\ast }\right|}}$$\ve_\rm r^* = \dfrac{\ve^*}{\vqty{x^*}}$.

• 有效数字

  • 对于 $x^{\ast }=\pm {10}^m\times (a_1+a_2\times {10}^{-1}+\cdots +a_l\times {10}^{-l-1})$$x^* = \pm 10^m \cp (a_1 + a_2 \cp 10\inv + \cdots + a_l \cp 10^{-{l-1}})$，

  • 若具有 $n$$n$ 位有效数字，则其相对误差限 ${\epsilon }_{\mathrm{r}}^{\ast }\le {\displaystyle \frac{1}{2a_1}}\times {10}^{-n-1}$$\ve_\rm r^* \le \dfrac{1}{2a_1} \cp 10^{-{n-1}}$.

  • 若相对误差限 ${\epsilon }_{\mathrm{r}}^{\ast }\le {\displaystyle \frac{1}{2(a_1+1)}}\times {10}^{-(n-1)}$$\ve_\rm r^* \le \dfrac{1}{2 (a_1 + 1)} \cp 10^{-(n-1)}$，则至少具有 $n$$n$ 位有效数字.

• 误差估计

  • 一元：$\epsilon (f(x^{\ast }))\approx |f^{\prime }(x^{\ast })|\epsilon (x^{\ast })$$\ve\pqty{f(x^*)} \approx \vqty{f'(x^*)} \ve(x^*)$.

  • 二元：

    下列式子也仅是在误差限较小时才近似成立.

    • $\epsilon (x_1^{\ast }\pm x_2^{\ast })\le \epsilon (x_1^{\ast })+\epsilon (x_2^{\ast })$$\ve(x_1^* \pm x_2^*) \le \ve(x_1^*) + \ve(x_2^*)$.

    • $\epsilon (x_1^{\ast }{x}_2^{\ast })\le \left|x_1^{\ast }\right|\epsilon (x_2^{\ast })+\left|x_2^{\ast }\right|\epsilon (x_1^{\ast })$$\ve(x_1^* x_2^*) \le \vqty{x_1^*} \ve(x_2^*) + \vqty{x_2^*} \ve(x_1^*)$.

    • $\epsilon (x_1^{\ast }/x_2^{\ast })\le {\displaystyle \frac{\left|x_1^{\ast }\right|\epsilon (x_2^{\ast })+\left|x_2^{\ast }\right|\epsilon (x_1^{\ast })}{{\left|x_2^{\ast }\right|}^2}},x_2^{\ast }\ne 0$$\ve(x_1^* / x_2^*) \le \dfrac{\vqty{x_1^*} \ve(x_2^*) + \vqty{x_2^*} \ve(x_1^*)}{\vqty{x_2^*}^2}, \quad x_2^* \ne 0$.

  • 多元：$\epsilon (A^{\ast })\approx {\displaystyle \sum _{k=1}^n\left|{\left({\displaystyle \frac{\partial f}{\partial x_k}}\right)}^{\ast }\right|\epsilon (x_k^{\ast })}$$\ve(A^*) \approx \knsum \vqty{\pqty{\dpdv{f}{x_k}}^*} \ve(x_k^*)$.

在我们的课程中，约定：

• 准确值：$x^{\ast }$$x^*$.

• 近似值：$x$$x$.

• 绝对误差：$e_x=x^{\ast }-x$$e_x = x^* - x$.

其他概念基本相同.

1.3 误差分析与减小

• 分析方法

  • 定性分析

  • 概率分析法

  • 向后误差分析法

  • 区间分析法

• 良好的近似值

  • 数值稳定性：计算过程中舍入误差不增长.

  • 病态问题：即输入数据的微小扰动引起输出数据相对误差很大的问题.

    病态性是数值问题自身固有的，而非计算方法引起.

    稳定性是计算方法引起的，而非数值问题自身固有.

  • 条件数（相对误差比值）

    • $C_p=\left|{\displaystyle \frac{f(x)-f(x^{\ast })}{f(x)}}\right|/\left|{\displaystyle \frac{\mathrm{\Delta }x}{x}}\right|\approx \left|{\displaystyle \frac{x{f}^{\prime }(x)}{f(x)}}\right|$$C_p = \vqty{\dfrac{f(x) - f(x^*)}{f(x)}} \left/ \vqty{\dfrac{\Delta x}{x}} \right. \approx \vqty{\dfrac{x f'(x)}{f(x)}}$.

    • 若 $C_p\ge 10$$C_p \ge 10$，则认为是病态的.

  • 若使用稳定的算法计算良态问题，并选择合适的初始值，则可以得到良好的近似.

• 减小误差

  • 避免两相近数相减，如

    • $\sqrt{x+1}-\sqrt{x}={\displaystyle \frac{1}{\sqrt{x+1}+\sqrt{x}}}$$\sqrt{x+1} - \sqrt x = \dfrac{1}{\sqrt{x+1} + \sqrt{x}}$.

      若解二次方程，则可利用 $x_1{x}_2=a$$x_1 x_2 = a$，原理相同.

    • $1-\cos x=2{\sin }^2{\displaystyle \frac{x}{2}}$$1 - \cos x = 2 \sin[2] \dfrac{x}{2}$.

    • $\ln x_1-\ln x_2=\ln {\displaystyle \frac{x_1}{x_2}}$$\ln x_1 - \ln x_2 = \ln\dfrac{x_1}{x_2}$.

    • $f(x)-f(x^{\ast })=f^{\prime }(x^{\ast })(x-x^{\ast })+\cdots$$f(x) - f(x^*) = f'(x^*) (x - x^*) + \cdots$

  • 避免用绝对值很小的数做除数.

  • 减少运算次数，或加快收敛速度. 如

    • $\ln {\displaystyle \frac{1+x}{1-x}}=2(x+{\displaystyle \frac{x^3}{3}}+{\displaystyle \frac{x^5}{5}}+\cdots +{\displaystyle \frac{x^{2n+1}}{2n+1}}+\cdots )$$\ln\dfrac{1+x}{1-x} = 2 \pqty{ x + \dfrac{x^3}{3} + \dfrac{x^5}{5} + \cdots + \dfrac{x^{2n+1}}{2n+1} + \cdots }$.

    • $\pi$$\pi$.

  • 改变运算次序：如一个大数与若干小数相加，先算较小数相加.

1.4 常用方法

• 秦九韶算法

  • 对于 $p(x)=a_0{x}^n+\cdots +a_{n-1}x+a_n$$p(x) = a_0 x^n + \cdots + a_{n-1} x + a_n$，

  • 多项式值

    • $\{\begin{array}{l}{b}_0=a_0,\\ b_i=b_{i-1}{x}^{\ast }+a_i,& i=1,2,\cdots ,n.\end{array}$$\begin{cases} b_0 = a_0, \\ b_i = b_{i-1} x^* + a_{i}, & i = \oneton. \end{cases}$

    • $p(x^{\ast })=b_n$$p(x^*) = b_n$.

  • 导数的值

    • $p(x)=(x-x^{\ast })(b_0{x}^{n-1}+\cdots +b_{n-1})+b_n$$p(x) = (x-x^*) (b_0 x^{n-1} + \cdots + b_{n-1}) + b_n$.

    • $p^{\prime }(x^{\ast })=b_0{x}^{n-1}+\cdots +b_{n-2}x+b_{n-1}$$p'(x^*) = b_0 x^{n-1} + \cdots + b_{n-2} x + b_{n-1}$.

    • $\{\begin{array}{l}{c}_0=b_0,\\ c_i=c_{i-1}{x}^{\ast }+b_i,& i=1,2,\cdots ,n.\end{array}$$\begin{cases} c_0 = b_0, \\ c_i = c_{i-1} x^* + b_{i}, & i = \oneton. \end{cases}$

    • $p^{\prime }(x^{\ast })=c_n$$p'(x^*) = c_n$.

• 迭代法

  • $x_{n+1}={\displaystyle \frac{1}{2}}(x_n+{\displaystyle \frac{a}{x_n}}),\underset{n\to \mathrm{\infty }}{lim}{x}_n=\sqrt{a}$$x_{n+1} = \dfrac{1}{2} \pqty{x_n + \dfrac{a}{x_n}}, \quad \nlim x_n = \sqrt{a}$.

    一般 4~5 次迭代就能达到 ${10}^{-8}$$10^{-8}$ 的精度.

  • $x_{n+1}={\displaystyle \frac{1}{k}}((k-1)x_n+{\displaystyle \frac{a}{x_n^{k-1}}}),\underset{n\to \mathrm{\infty }}{lim}{x}_n=\sqrt[k]{a}$$x_{n+1} = \dfrac{1}{k} \pqty{ (k - 1) x_n + \dfrac{a}{x_n^{k-1}} }, \quad \nlim x_n = \sqrt[k]a$.

    上二式本质上是牛顿迭代法.

• 以直代曲

  • 割圆术.

  • 牛顿迭代法：$x_{n+1}=x_n-{\displaystyle \frac{f(x_n)}{f^{\prime }(x_n)}}$$x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$.

  • 定积分的梯形公式：$T_n={\displaystyle \sum _{i=1}^n{\displaystyle \frac{h}{2}}[f(x_{i-1})+f(x_i)]}$$T_n = \insum \dfrac{h}{2} \bqty{f(x_{i-1}) + f(x_i)}$.

• 松弛法：$\bar{a}=a_n+\omega (a_n-a_{n-1})$$\overline a = a_n + \omega (a_n - a_{n-1})$. 以复化求积公式为例，

  • $T_1={\displaystyle \frac{x_1-x_0}{2}}[f(x_0)+f(x_1)]$$T_1 = \dfrac{x_1 - x_0}{2} \bqty{f(x_0) + f(x_1)}$.

  • $T_2={\displaystyle \frac{x_2-x_0}{4}}[f(x_0)+2f(x_1)+f(x_2)]$$T_2 = \dfrac{x_2 - x_0}{4} \bqty{f(x_0) + 2f(x_1) + f(x_2)}$.

  • $S_1=T_2+{\displaystyle \frac{T_2-T_1}{3}}={\displaystyle \frac{x_2-x_0}{6}}[f(x_0)+4f(x_1)+f(x_2)]$$S_1 = T_2 + \dfrac{T_2 - T_1}{3} = \dfrac{x_2 - x_0}{6} \bqty{f(x_0) + 4f(x_1) + f(x_2)}$.